package xyf.p10.dp;

/**
 * ClassName: P0213_Rob
 * Description:
 * Author: xyf
 * Date: 9/9/22 10:27 AM
 * Version: 1.0
 **/
public class P0213_Rob
{
    public int rob(int[] nums)
    {
        if (nums == null || nums.length <= 0)
        {
            return -1;
        }

        if (nums.length == 1)
        {
            return nums[0];
        }
        if (nums.length == 2)
        {
            return Math.max(nums[0], nums[1]);
        }

        int max1 = nums[0] + rob(nums, 2, nums.length - 2);
        int max2 = rob(nums, 1, nums.length - 1);

        return Math.max(max1, max2);
    }


    public int rob(int[] nums, int start, int end)
    {
        if (start > end || start >= nums.length - 1)
        {
            return 0;
        }

        int[][] dp = new int[nums.length][2];
        dp[start][0] = 0;
        dp[start][1] = nums[start];

        int max = Math.max(dp[start][0], dp[start][1]);
        for (int i = start + 1; i <= end; i++)
        {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + nums[i];

            max = Math.max(dp[i][0], max);
            max = Math.max(dp[i][1], max);
        }
        return max;
    }
}